package com.jack.leetcode.每日一题;

import java.util.*;

public class 课程表2 {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] deepth = new int[numCourses];
        int n = prerequisites.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            deepth[prerequisites[i][0]]++;
            if (map.containsKey(prerequisites[i][1])) {
                map.get(prerequisites[i][1]).add(prerequisites[i][0]);
            } else {
                List<Integer> mapList = new ArrayList<>();
                mapList.add(prerequisites[i][0]);
                map.put(prerequisites[i][1], mapList);
            }
        }

        List<Integer> result = new ArrayList<>();
        Stack<Integer> queue = new Stack<>();
        for (int i = 0; i < numCourses; i++) {
            if (deepth[i] == 0) {
                queue.add(i);
            }
        }
        while (queue.size() != 0) {
            int cur = queue.pop();
            result.add(cur);
            List<Integer> next = map.get(cur);
            if (next != null && !next.isEmpty()) {
                next.forEach(t -> {
                    deepth[t]--;
                    if (deepth[t] == 0) {
                        queue.add(t);
                    }
                });

            }
        }
        return result.size() == numCourses ? result.stream().mapToInt(Integer::intValue).toArray() : new int[0];
    }
}
